Various processes have been developed to determine the extreme value(s) (i.e., a minimum or maximum) of a plurality of values. One such method includes a sequential comparison, whereby the values are arranged in a list and each value in the list is compared to the minimum of the previous values of the list. The number of steps needed to perform a sequential comparison of n values is on the order of O(n) steps. Another known sorting process includes maintaining a sorted queue, whereby each of the plurality of values is less than or equal to one of its neighboring values and greater than or equal to its other neighboring value. Accordingly, the extraction of either the minimum or maximum value of the sorted queue is on the order of O(1) steps, while inserting a value into the sorted queue is on the order of O(n) steps.
Another sorting method combining the benefits of both the unsorted and sorted queues includes generating and maintaining a heap data structure. In a minimum heap data structure, each parent node of the heap is either less than or equal to its child nodes. This results in the minimum value of the heap being at the root node of the heap. Therefore, the identification of the minimum value in a proper heap is on the order of O(1). However, the extraction or modification of the minimum value from a heap of n values is on the order of O(log n) steps, as is the insertion of a new value into the heap data structure.
Heap data structures and/or other sorting processes often are used in network processors to implement various scheduling processes, such as Weighted Fair Queuing (WFQ) or Generalized Processor Scheduling (GPS), to ensure that each incoming data stream receives a certain portion of the outgoing data stream bandwidth and/or to provide a latency bound for each incoming data stream. For example, a common method to implement WFQ scheduling is to associate a “due timestamp” value with each of the input queues used to buffer the incoming data streams. For each output cycle, a WFQ scheduler selects the input queue with the minimum “due timestamp” to provide a protocol data unit (PDU) for output. During or after the transmission of the PDU (e.g., a data packet) from the selected queue, the scheduler updates the “due timestamp” of the selected queue based at least in part on the assigned bandwidth and the size of the current PDU in the selected queue. Accordingly, a minimum heap data structure or a sorted queue often is used to determine the minimum “due timestamp” of the plurality of input queues as well as the index associated with the queue.
While priority queues, such as sorted queues or heap data structures, often are useful in scheduling processes, the insertion, removal, and/or maintenance of such priority queues often consumes a considerable portion of the processing cycles of a processor implementing the scheduling process. For example, to determine the minimum value in an unsorted queue, at least one compare instruction and one jump instruction typically are performed for each comparison of a value in the queue to the minimum of the previous values. As such, at least 2n instructions are performed to identify the minimum value and/or its index in the queue. Similarly, for heap data structures, the insertion of a new value (such as when the “due timestamp” for an input queue is modified) into the heap data structure or a removal of a value often necessitates a branch instruction and a jump instruction for each comparison of a parent node to a child node. Since O(log n) comparisons typically are performed when inserting/removing a value into/from a heap data structure of n values, the typical insertion/removal operation takes at least 2 log n cycles to perform.
Accordingly, an improved processor instruction, method, and/or system for determining an extreme value of a plurality of values in a heap or other priority queue would be advantageous.